package cn.icatw.leetcode.editor.cn;
//给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
//
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//
// 返回容器可以储存的最大水量。
//
// 说明：你不能倾斜容器。
//
//
//
// 示例 1：
//
//
//
//
//输入：[1,8,6,2,5,4,8,3,7]
//输出：49
//解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
//
// 示例 2：
//
//
//输入：height = [1,1]
//输出：1
//
//
//
//
// 提示：
//
//
// n == height.length
// 2 <= n <= 10⁵
// 0 <= height[i] <= 10⁴
//
//
// Related Topics 贪心 数组 双指针 👍 5026 👎 0


//Java：盛最多水的容器
public class T11_ContainerWithMostWater {
    public static void main(String[] args) {

        Solution solution = new T11_ContainerWithMostWater().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxArea(int[] height) {
             /*
        * 解题思路
使用双指针法解决这个问题。我们将两个指针分别放在数组的两端，然后向中间移动，计算每次可能的最大面积，最终找到最大的面积。

具体步骤如下：

初始化两个指针：左指针 left 指向数组的最左端，右指针 right 指向数组的最右端。
计算面积并移动指针：
计算当前左指针和右指针指向的高度之间的容器面积。
更新最大面积。
移动较低的一侧的指针向中间靠拢，以期找到更高的边界，可能容纳更多的水。
重复步骤2，直到两个指针相遇。
        * */
            int left = 0, right = height.length - 1;
            int maxArea = 0;
            while (left < right) {
                int area = Math.min(height[left], height[right]) * (right - left);
                maxArea = Math.max(maxArea, area);
                if (height[left] < height[right]) {
                    left++;
                } else {
                    right--;
                }
            }
            return maxArea;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
